package Leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @ Author     ：侯耀祖
 * @ Description：
 */
public class permute {
    // 存储所有可能的排列结果
    List<List<Integer>> result = new ArrayList<>();
    // 存储当前正在构建的排列路径
    LinkedList<Integer> path = new LinkedList<>();
    // 标记数组中的元素是否被使用过
    boolean[] used;

    /**
     * 计算给定数组的所有排列
     * @param nums 给定的数组
     * @return 所有可能的排列
     */
    public List<List<Integer>> permute(int[] nums) {
        // 初始化used数组，表示每个元素都未被使用
        used = new boolean[nums.length];
        // 开始回溯计算排列
        backtrack(nums);
        return result;
    }

    /**
     * 回溯函数，用于计算排列
     * @param nums 给定的数组
     */
    public void backtrack(int[] nums){
        // 如果当前路径长度等于数组长度，说明找到了一个完整的排列
        if (path.size() == nums.length){
            // 将当前路径添加到结果中，需要创建一个新的ArrayList以避免后续修改影响
            result.add(new ArrayList<>(path));
            return;
        }
        // 遍历数组中的每个元素
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            // 如果当前元素已被使用，则跳过
            if (used[i]){
                continue;
            }
            // 标记当前元素已被使用
            used[i] = true;
            // 将当前元素添加到路径中
            path.add(num);
            // 递归调用回溯函数，继续构建排列
            backtrack(nums);
            // 回溯，移除最后一个添加的元素，以便尝试其他可能的排列
            path.removeLast();
            // 取消当前元素的使用标记
            used[i] = false;
        }
    }
}
